◀ Prev · Parts · Full · Next ▶

The problem was first suggested and solved in O ( V log ⁡ ⁡ V ) {\displaystyle O(V\log V)} time in 1983 by Gallager et al.,cite-ref-ghs-1-0[1] where V {\displaystyle V} is the number of vertices in the graph. Later, the solution was improved to O ( V ) {\displaystyle O(V)} cite-ref-2[2] and finallycite-ref-3[3]cite-ref-4[4] O ( V log ∗ ∗ ⁡ ⁡ V + D ) {\displaystyle O({\sqrt {V}}\log ^{*}V+D)} where D is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to becite-ref-5[5] Ω Ω ( V log ⁡ ⁡ V + D ) . {\displaystyle \Omega \left({{\frac {\sqrt {V}}{\log V}}+D}\right).}

• Overview

• MST in message-passing model

• GHS algorithm

• Assumptions

• Properties of MSTs

• Description of the algorithm

• Progress property

• Approximation algorithms

• References

◀ Prev · Parts · Full · Next ▶